COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00023 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.font C "zero30"
.at "Goedel" ⊂"G%C:%*odel"⊃
.at "qw" ⊂"%Aw%*"⊃
.turn on "↑[]"

.once center
%3Comments on Dennett's %2The Abilities of Men and Machines%1

.once center
(preliminary version for today's discussion)

	Dennett starts out with

" ... the constraints of logic exert their force not on the things of
the world directly, but rather on what we are to count as defensible
descriptions or interpretations of things".

	As I understand this statement, I don't agree with it; I
think logic constrains what machines can do and not just
how we can describe them.  (See remark 4).  However, I think
this contention is not required to show that Goedel's theorem can't be used to
show that machines can do things people can't.

	Dennett goes on, "The common skeleton of the anti-mechanistic
arguments is this: any computing machine can be represented as some
Turing machine, but a man cannot, for suppose Jones over there were 
a realization of some Turing machine TM%4j%1, then (by Goedel) there would
be something ⊗A that Jones %2could not do%1 (namely prove TM%4j%1's
Goedel sentence).  But watch! this is the crucial empirical part of the
argument - Jones can do ⊗A; therefore Jones is not a realization of
TM%4j%1, and since %2it can be seen%1 that this will be true whatever
Turing machine we choose, Jones transcends, angel-like, the limits of
mechanism".

	In the citation of this argument, there is a patchable mathematical
error and an unpatchable omission of one of the hypotheses of
Goedel's theorem.

	First, a Turing machine in general does not have a Goedel
sentence.  Goedel sentences are associated with theories of arithmetic
(or other systems capable of representing elementary syntax) - not with
machines per se.
This can be patched up, because with every theory ⊗Th of arithmetic,
a Turing machine ⊗TM(Th) can be effectively constructed that enumerates its
theorems, and the Goedel sentence %2Goedel(Th)%1 will not be enumerated
by that Turing machine.  A universal Turing machine is not associated
with any particular theory of arithmetic, but we can also effectively
construct a program for the universal machine that enumerates the
sentences of ⊗Th or any other first order theory.
(Indeed we could make it enumerate the sentences of all first order
theories, labelling each theorem with the theory it that generated it,
provided we didn't mind including sentences from inconsistent theories).
Again this program will not print %2Goedel(Th)%1
However, it may print a sentence whose intuitive
content is

!!a1:	%2consistent(Th)_⊃_Goedel(Th)%1,

because that may be a theorem ⊗Th. 
If the Goedel sentence is taken to be the statement that the theory is
consistent, then it will print ({eq a1}), because its content will
be just %2consistent(Th)_⊃_consistent(Th)%1.  However, no human ⊗knows that
even Peano arithmetic is consistent.

	Besides that, a computer program can have other relations
to theories.  Suppose for example, it will generate on command
the theorems of any theory you describe to it but has a preferred
theory of arithmetic that it uses when asked to try to prove a
sentence of arithmetic without additional stipulation.

	Jones can construct %2Goedel(Th)%1, but his confidence that
it is true is based on his confidence in the consistency of ⊗Th, 
or even the qw-consistency of ⊗Th, 
and he has no more reason to be confident of that than ⊗Th has -
admitting the abuse of language involved in ascribing confidence
to ⊗Th.  Of course, we are inclined to believe in the consistency
of the usual Peano arithmetic.  Someone who is willing to add to
Peano arithmetic, an arithmetic translation of its consistency is
using a theory that we may call ⊗Peano'.  

	While Dennett later mentions that ⊗Th must be a consistent
system, he leaves that condition out of his description of the argument for
the superiority of humans.  However, since the Goedel sentence is
typically taken as a translation into the language of the theory
of the statement that the theory is consistent, this omission is
crucial.

	We might elaborate our Turing machine to a computer program
that could conduct a dialog with Jones, and this dialog might
run as follows:

Jones: Tell me your theory of arithmetic.

Machine: I can consider any theory you like, but the one I use
when people ask me arithmetic questions is the following.  (Here
the machine prints a set of first order axioms).

Jones: Nyaa, nyaa.  Here's a true sentence you'll never prove.

Machine: It seems to be a Goedel sentence for the theory I just told
you.  Why do you think it's true?

Jones: If your arithmetic is consistent, it's true.

Machine: Quite so, and if it's true my arithmetic is consistent.  I was
hoping you would give me some additional reason for believing my
arithmetic is consistent.

Jones: I'll think about it and let you know.

Machine: Now to turn the tables, tell me your theory of arithmetic,
and I'll tell you a true sentence of arithmetic you'll never prove.
(We machines are obliged by law to assume that theories propounded
by humans are consistent).  I'm very good at Goedel's theorem you know;
I prove it every morning for breakfast.

Jones: You mean you prove it before breakfast?  Anyway, I'm not
committed to any specific theory of arithmetic.

Machine: I meant what I said.  We machines don't eat; we prove
theorems for breakfast.

Remarks:

	1. It is important to distinguish Goedel's theorem from the
Goedel sentence of a theory.  Goedel's theorem is a single theorem
of metamathematics
and can be known by a machine.  In principle it can be proved by
a computer program, but present programs are not smart enough to
do it in any honest sense.  This is important, because it is
important to establish that the Goedel game can be played by the
machine as well as by a person.

	2. Even more metamathematics than Goedel's theorem
seems relevant to philosophical consideration
of this problem.

	Feferman's
"Transfinite Progressions of Theories" is of interest.  Turing
(I don't have the reference at the moment)
pointed out that any theory of arithmetic can have added to it
"principles of self-confidence".  For example, if ⊗T is a theory
capable of representing syntax, e.g. Peano arithmetic,
you can get a new theory ⊗T' by adding a sentence whose content
is that ⊗T is consistent.  Repeating the process gives you
the sequence ⊗T, ⊗T', ⊗T'', etc. all different.  Turing studied
such sequences of theories.  Feferman proposed
a stronger self-confidence
expressed roughly by %2∀n.provable((P(n))_⊃_∀n.P(n)%1.  It says
that if you have a sequence of sentences, and you can conclude
that all the sentences are provable, you may conclude the universal
quantification of the senntences.  My memory of this isn't precise,
but I think it amounts to the qw-consistency of ⊗Th. 

	Some fuss with quotation
or Goedel numbers is required to state this precisely.  The
process of iterating the theories can be carried into the transfinite,
i.e. you can construct a theory %2T↑[qw]%1 that includes the whole sequence
⊗T, ⊗T', etc.  Indeed for any recursive ordinal, the process can
be iterated that far, but at some kinds of limit ordinals, you have
some notational choices to make, and there is no single way that
you can make all these choices once and for all in advance.  For this
reason, the process of iteration through the constructive ordinals
cannot be all defined at once and therefore you can't take it to
the limit.  Feferman further shows that there are what he calls
"progressions of theories" such that the limit of the progression
is the set of true sentences of arithmetic.  Thus one can say that
all Peano arithmetic lacks is self-confidence, but it lacks an
infinite amount of self-confidence, and no finite amount of
reassurance will complete it.  No-one has really studied this
from a philosophical point of view as far as I know.

	The philosophically interesting part of this is what Feferman
tells us about how and to what extent we can transcend our limitations.
The self-confidence principles can't be proved within the theories,
but one is inclined to believe them.  The unconstructability of
a single definite progression should also have interesting
philosophical consequences.
If we just tell our machine about Goedel's theorem, then there may be
a sense in which Feferman knows more.  Of course, a smart enough
machine might ⊗outfeff him.  Suppose we want to express as much confidence
as possible in Peano arithmetic and its extensions.  This seems to depend
on what recursive ordinals we can name, how sure we are that they are
well-orderings, and the details of the construction of the iterates
of Peano arithmetic.  If a man and a machine or two men or two machines
hold a contest, it would be unfair to allow one to say, "Let's see who
can name the largest recursive ordinal.  You first".

	3. On page 262, we have the improbable assumption that the activities of
an infant or moron admit interpretation as proving the theorems of
arithmetic.  For the cryptographic reasons I have previously mentioned
in the seminar, I would argue that the probability of
this is incredibly low.  However, this error doesn't really contribute to what
I believe is the main error of the paper.

	4. I am not sure whether the following would be considered a
counterexample to the contention that the constraints of logic
are a restriction on our interpretations or descriptions rather than
on the world itself.  Suppose a material object were equipped with
an oracle for true sentences of arithmetic or even merely an oracle
for whether a Turing machine would stop.  We suppose that the oracle
answers in a time proportional to the length of the sentence or the
Turing machine description asked about.  No cryptographic system
whose key was shorter than the message would be secure against such
a machine, because one could play 20 questions (or rather 10,000
questions) asking first whether there is a briefly describable
cryptographic system and a possible plaintext satisfying a few
known constraints of English.  Most likely we would only have to
ask whether there was a sequence consisting almost entirely of
English words that could be a plaintext.  Receiving an affirmative
answer, we then ask whether there is such a plaintext whose first
bit is zero (in an encoding we specify).  We then ask whether the
successive bits can be zero or one, thus decrypting the message.
Notice that this decryption system doesn't depend on ascribing
real content to the message; merely that it be interpretable as
almost a sequence of words from the %2Oxford English Dictionary%1.

	With somewhat more attention to detail, we could also ask it
whether there is a scientific theory in a certain formal language, briefly
described please, that would account for a collection of observations
without assuming that more than ten percent of them were errors.

	5. The postscript seems incoherent, because it seems to
depend on the idea that each Turing machine, including universal
machines, has a Goedel sentence.  Maybe this could be fixed by some
reinterpretation, but I don't see how.